| 翻訳と辞書 |
| Suurballe's algorithm ： ウィキペディア英語版 |
Suurballe's algorithm
In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length.〔.〕 The algorithm was conceived by John W. Suurballe and published in 1974.〔.〕 The main idea of Suurballe's algorithm is to use Dijkstra's algorithm to find one path, to modify the weights of the graph edges, and then to run Dijkstra's algorithm a second time. The modification to the weights is similar to the weight modification in Johnson's algorithm, and preserves the non-negativity of the weights while allowing the second instance of Dijkstra's algorithm to find the correct second path.
The objective is strongly related to that of minimum cost flow algorithms, where in this case there are two units of "flow" and nodes have unit "capacity".
==Definitions==
Let be a weighted directed graph containing a set of vertices and a set of directed edges; let be a designated source vertex in , and let be a designated destination vertex. Let each edge in , from vertex to vertex , have a non-negative cost .
Define to be the cost of the shortest path to node from node in the shortest path tree rooted at .
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Suurballe's algorithm」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|